import java.util.HashMap;
import java.util.Map;

/**
 * @author kaho
 * @since 2020/12/28
 */
public class _188_买卖股票的最佳时机_IV {

    /**
     * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
     * <p>
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
     * <p>
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：k = 2, prices = [2,4,1]
     * 输出：2
     * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
     * 示例 2：
     * <p>
     * 输入：k = 2, prices = [3,2,6,5,0,3]
     * 输出：7
     * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     * 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        return dfs(0, 0, 0, k, prices);
    }

    //计算k次交易，index表示当前是哪天，status是买卖状态，coutnt为交易次数
    private static int dfs(int index, int status, int count, int k, int[] prices) {
        if (index == prices.length || count == k) {
            return 0;
        }
        int a = 0, b = 0, c = 0;
        //保持不动
        a = dfs(index + 1, status, count, k, prices);
        if (status == 1) {
            //卖一股，并将交易次数+1
            b = dfs(index + 1, 0, count + 1, k, prices) + prices[index];
        } else {
            //买一股
            c = dfs(index + 1, 1, count, k, prices) - prices[index];
        }
        return Math.max(Math.max(a, b), c);
    }

    public static void main(String[] args) {
        int[] i = {6,1,3,2,4,7};
        int i1 = maxProfit1(2, i);
    }

    public static int maxProfit1(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        if (k > prices.length / 2) {
            int dep = 0, dep1 = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                dep = Math.max(dep, dep1 + prices[i]);
                dep1 = Math.max(dep1, dep - prices[i]);
            }
            return Math.max(dep, dep1);
        }
        Map<Key, Integer> cache = new HashMap<>();
        return dfsCache(cache, 0, 0, 0, k, prices);
    }

    private static int dfsCache(Map<Key, Integer> cache, int index, int status, int count, int k, int[] prices) {
        Key key = new Key(index, status, count);
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        if (index == prices.length || count == k) {
            return 0;
        }
        int a = 0, b = 0, c = 0;
        a = dfsCache(cache, index + 1, 0, count , k, prices);
        if (status == 1) {
            b = dfsCache(cache, index + 1, 0, count + 1, k, prices) + prices[index];

        } else {
            c = dfsCache(cache, index + 1, 1, count , k, prices) - prices[index];

        }
        cache.put(key, Math.max(Math.max(a, b), c));
        return cache.get(key);
    }

    //Key对象封装了index、status、交易次数count，作为map的key
    private static class Key {
        private final int index;
        private final int status;
        private final int count;

        Key(int index, int status, int count) {
            this.index = index;
            this.status = status;
            this.count = count;
        }

        //这里需要实现自定义的equals和hashCode函数
        public int hashCode() {
            return this.index + this.status + this.count;
        }

        public boolean equals(Object obj) {
            Key other = (Key) obj;
            if (index == other.index && status == other.status && count == other.count) {
                return true;
            }
            return false;
        }
    }
}
